#include "ContextFreeGrammar_LL.h"

#include <vector>
#include <cassert>
#include <algorithm>

ContextFreeGrammar_LL::ContextFreeGrammar_LL(std::istream & in) : ContextFreeGrammar(in)
{
    //ctor
}

ContextFreeGrammar_LL::~ContextFreeGrammar_LL()
{
    //dtor
}


void ContextFreeGrammar_LL::LeftFactoring()
{
    bool hasChanged = false;
    do
    {
        hasChanged = false;

        for(auto itr = nonterminal.begin(); itr != nonterminal.end(); ++itr)
        {
            ProductionList lngstCmnPfx;
            ProductionMap::iterator bitr, eitr;
            std::tie(bitr, eitr) = this->production.equal_range(*itr);

            if(std::next(bitr) == eitr)
                continue;

            size_t shortest = bitr->second.size();
            std::vector <ProductionList::iterator> listIters;
            listIters.reserve(std::distance(bitr, eitr));
            for(auto pitr = bitr; pitr != eitr; ++pitr)
                shortest = std::min(shortest, pitr->second.size()), listIters.push_back(pitr->second.begin());
            listIters.shrink_to_fit();
            assert(shortest > 0);

            for(size_t i = 0; i < shortest; ++i)
            {
                bool isCommon = true;
                for(auto litr = std::next(listIters.begin()); litr != listIters.end(); ++litr)
                {
                    auto prevlitr = std::prev(litr);
                    if(*prevlitr != *litr)
                        isCommon = false;
                }

                if(!isCommon)
                    break;

                lngstCmnPfx.push_back(**listIters.begin());
            }

            if(lngstCmnPfx.empty())
                continue;

            std::cerr << "Common prefix found :" ;
            this->PrintProductionRight(lngstCmnPfx, std::cerr);

            std::string newname = this->GenerateUniqueName(*itr + "_lf");
            auto nameitr = nonterminal.insert(newname).first;

            production.insert(std::make_pair(newname, lngstCmnPfx));
        }

    }while(hasChanged);
}

void ContextFreeGrammar_LL::EliminateNullable()
{
    bool hasNullable = false;
    do
    {
        hasNullable = false;
        std::set <std::string> nullable;
        for(auto itr = production.begin(); itr != production.end(); ++itr)
            if(*(itr->second.begin()) ==  GetEpsilon())
                if((itr->second.size()) == 1)
                {
                    hasNullable = true;
                    nullable.insert(itr->first);
                    std::cerr << "Nullable found:" << itr->first << std::endl ;
                }
        for(auto itr = production.begin(); itr != production.end();)
            if(*(itr->second.begin()) ==  GetEpsilon() && (itr->second.size()) == 1)
                itr = production.erase(itr);
            else
                ++itr;

        std::list <std::pair<std::string, ProductionList>> newLists;
        for(auto itr = production.begin(); itr != production.end(); ++itr)
        {
            const auto & plist = itr->second;
            size_t nullcnt = std::count_if(plist.begin(), plist.end(),
                                        [this, nullable](StringSet::const_iterator elem){return nullable.find(*elem) != nullable.end();});

            if(nullcnt >= 64)
                throw std::runtime_error("Too much nullables");

            for(unsigned long long subset = 0; subset < (1ULL << nullcnt); subset++)
            {
                ProductionList newPlist;
                int cnt = 0;
                for(auto jtr = plist.begin(); jtr != plist.end(); ++jtr)
                {
                    if(nullable.find(**jtr) == nullable.end())
                        newPlist.push_back(*jtr);
                    else
                    {
                        if((1 << cnt) & subset)
                            newPlist.push_back(*jtr);
                        cnt++;
                    }
                }
                assert(cnt == nullcnt);
                if(!newPlist.empty())
                    newLists.push_back(std::make_pair(itr->first, newPlist));
            }
        }
        std::for_each(newLists.begin(), newLists.end(),
                      [this](const std::pair<std::string, ProductionList> & p){
                      bool found = false;
                      ProductionMap::iterator bitr, eitr;
                      std::tie(bitr,eitr) = production.equal_range(p.first);
                      for(auto itr = bitr; itr != eitr; ++itr)
                        if(itr->second.size() == p.second.size() && itr->second == p.second){
                            found = true;
                            break;
                        }

                      if(!found)
                        production.insert(p);
                      });

        //PrintProduction();
    }while(hasNullable);
}


void ContextFreeGrammar_LL::EliminateLeftRecur()
{
    auto nonterminal_old = this->nonterminal;

    for(auto i = nonterminal_old.begin(); i != nonterminal_old.end(); ++i)
    {
        //std::cerr << *i << " :" ;

        std::list <ProductionList> newProductions;
        std::list <ProductionMap::iterator> erasureMarker;

        ProductionMap::iterator bitr, eitr;
        std::tie(bitr, eitr) = production.equal_range(*i);

        std::cerr << "Replacing " << *i << std::endl ;
        std::cerr << "Productions:" << std::endl ;
        PrintProduction();

        for(auto j = nonterminal_old.begin(); j != i; ++j)
        {
            //std::cerr << " " << *j ;

            ProductionMap::iterator bitr2, eitr2;
            std::tie(bitr2, eitr2) = production.equal_range(*j);

            for(auto k = bitr; k != eitr; ++k)
                // if A_i -> A_j  gamma ...
                if(**(k->second.begin()) == *j)
                {
                    // Replace A -> A_j gamma ...
                    for(auto l = bitr2; l != eitr2; ++l)
                    {
                        // To Ai -> delta_n gamma
                        newProductions.emplace_back(l->second.begin(), l->second.end());

                        for(auto m = std::next(k->second.begin()); m != k->second.end(); ++m)
                            newProductions.rbegin()->push_back(*m);
                        PrintProductionRight({l->second.begin(), l->second.end()});
                    }

                    erasureMarker.push_back(k);
                    std::cerr << "Marking " << **(k->second.begin()) << " for erasure" << std::endl ;
                }

        }
        //std::cerr << std::endl ;
        std::cerr << "Erasing " << std::distance(erasureMarker.begin(), erasureMarker.end()) << " elements" <<std::endl;
        std::for_each(erasureMarker.begin(), erasureMarker.end(),
            [this](ProductionMap::iterator toErase){PrintProductionRight(toErase->second);
            std::cerr << std::endl ;production.erase(toErase);});
        std::cerr << "Inserting " << std::distance(newProductions.begin(), newProductions.end()) << " elements" <<std::endl;

        std::for_each(newProductions.begin(), newProductions.end(),
                      [this, i](const ProductionList & lst)
        {
            PrintProductionRight(lst);
            std::cerr << std::endl ;
            production.insert(std::make_pair(*i, lst));
        }
                     );
        this->EliminateLeftRecurSingle(i);

    }
}

void ContextFreeGrammar_LL::EliminateLeftRecurSingle(StringSet::const_iterator nonterm)
{
    std::cerr << "Elimination recurrence of " << *nonterm << " Productions :" ;
    PrintProduction();

    ProductionMap::iterator bitr, eitr;
    std::tie(bitr, eitr) = production.equal_range(*nonterm);
    std::list<ProductionList> alpha, beta;
    for(auto itr = bitr; itr != eitr; ++itr)
    {
        // nonterm and the iterator may not refer to the same set (c.f. EliminateLeftRecur())
        if(**(itr->second.begin()) == *nonterm)
        {
            auto titr = itr->second.begin();
            alpha.emplace_back(++titr, itr->second.end());
        }
        else
            beta.emplace_back(itr->second.begin(), itr->second.end());
    }

    if(alpha.empty())
        return;

    const std::string newname = this->GenerateUniqueName(*nonterm + "_lre");

    auto newitr = nonterminal.insert(newname).first;

    for(auto itr = beta.begin(); itr != beta.end(); ++itr)
        itr->push_back(newitr);
    for(auto itr = alpha.begin(); itr != alpha.end(); ++itr)
        itr->push_back(newitr);
    alpha.emplace_back(1, GetEpsilon());            // Append the epsilon at the end
/*
    std::cerr << "Alpha:";
    for(auto itr = alpha.begin(); itr != alpha.end(); ++itr)
    {
        std::cerr << std::endl ;
        PrintProductionRight(*itr);
    }
    std::cerr << std::endl << "Beta:";
    for(auto itr = beta.begin(); itr != beta.end(); ++itr)
    {
        std::cerr << std::endl ;
        PrintProductionRight(*itr);
    }
    std::cerr << std::endl ;
*/


    // Replace the productions
    production.erase(*nonterm);
    std::for_each(beta.begin(), beta.end(),
                  [this, &nonterm](const ProductionList & lst)
    {
        production.insert(std::make_pair(*nonterm, lst));
    }
                 );
    std::for_each(alpha.begin(), alpha.end(),
                  [this, &newname](const ProductionList & lst)
    {
        production.insert(std::make_pair(newname, lst));
    }
                 );
}
